package com.ddshuai.easy;

/**
 * 描述 新通教育
 *
 * @author ddshuai
 * @date 2018-09-28 上午9:24
 * <p>
 * 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
 * <p>
 * 注意：
 * <p>
 * num1 和num2 的长度都小于 5100.
 * num1 和num2 都只包含数字 0-9.
 * num1 和num2 都不包含任何前导零。
 * 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
 **/
public class AddStrings {

    /**
     * 效率很低
     *
     * @param num1
     * @param num2
     * @return
     */
    public static String addStrings(String num1, String num2) {
        String result = "";
        Integer needAddZeroCount = Math.abs(num1.length() - num2.length());
        String zeroStr = "";
        for (Integer i = 0; i < needAddZeroCount; i++) {
            zeroStr += "0";
        }
        if (num1.length() < num2.length()) {
            num1 = zeroStr + num1;
        } else {
            num2 = zeroStr + num2;
        }

        char[] array = num1.toCharArray();
        char[] array1 = num2.toCharArray();
        boolean needStep = false;

        for (int i = array.length; i > 0; i--) {
            Character a1 = array[i - 1];
            Character b1 = array1[i - 1];
            Integer sum = Integer.parseInt(a1.toString()) + Integer.parseInt(b1.toString());
            if (needStep) {
                sum = sum + 1;
                if (sum > 9) {
                    result = (sum - 10) + result;
                    needStep = true;
                } else {
                    result = sum + result;
                    needStep = false;
                }
            } else {
                if (sum > 9) {
                    result = (sum - 10) + result;
                    needStep = true;
                } else {
                    result = sum + result;
                    needStep = false;
                }
            }

        }
        if (needStep) {
            result = "1" + result;
        }
        return result;
    }

    public static String addStrings1(String num1, String num2) {
        char[] a = num1.toCharArray();
        char[] b = num2.toCharArray();
        if (a.length > b.length) {
            return addStrings1(a, b);
        } else {
            return addStrings1(b, a);
        }
    }

    /**
     * 提升了效率 超过了 89.88%
     * @param a
     * @param b
     * @return
     */
    public static String addStrings1(char[] a, char[] b) {
        char[] chars = new char[]{'0','1','2','3','4','5','6','7','8','9'};
        //从后往前加
        int less = a.length-b.length;
        int target = 0;
        for (int i = b.length-1; i >= 0; i--) {
            int sum = Integer.parseInt(String.valueOf(b[i]))+Integer.parseInt(String.valueOf(a[i+less]))+target;
            if (sum >9){
                a[i+less] = chars[(sum - 10)];
                target = 1;
            }else {
                a[i+less] = chars[sum];
                target = 0;
            }
        }
        //如果不需要进位 直接返回
        if (target == 0){
            return String.valueOf(a);
        }
        if (less > 0){
            exchange(a,less-1,chars);
            if (a[0] == '0'){
                return "1"+ String.valueOf(a);
            } else {
                return String.valueOf(a);
            }
        }

        return "1"+ String.valueOf(a);
    }

    public static boolean exchange(char[] a,int i,char[] nums){
        //当前位置 和 前一个位置是否是9
        if (a[i] == '9'){
            a[i] = '0';
            if (i > 0){
                exchange(a,i-1,nums);
            }
        }else {
            a[i] = nums[Integer.parseInt(String.valueOf(a[i]))+1];
        }
        return false;
    }

    /**
     * 效率最高的
     * @param num1
     * @param num2
     * @return
     */
    public static String addStrings2(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        for(int i=num1.length()-1,j=num2.length()-1;i>=0||j>=0||carry>0;i--,j--){
            int x = i<0?0:num1.charAt(i)-'0';
            int y = j<0?0:num2.charAt(j)-'0';
            int sum = x+y+carry;
            sb.append(sum%10);
            carry = sum/10;
        }
        return sb.reverse().toString();
    }
    public static void main(String[] args) {
        System.out.println(addStrings2("99", "9"));
    }
}
